﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ZuoAlgorithms.Class019;

// 展示acm风格的测试方式
// 子矩阵的最大累加和问题，不要求会解题思路，后面的课会讲
// 每一组测试都给定数据规模
// 需要任何空间都动态生成，在大厂笔试或者比赛中，这种方式并不推荐
// 测试链接 : https://www.nowcoder.com/practice/cb82a97dcd0d48a7b1f4ee917e2c0409?


public class Code02_SpecifyAmount
{
    // 求子矩阵的最大累加和
    public static int MaxSumSubmatrix(int[][] mat, int n, int m)
    {
        int max = int.MaxValue;
        for (int i = 0; i < mat.Length; i++)
        {
            int[] arr = new int[m];
            for (int j = i; j < n; j++)
            {
                for (int k = 0; k < m; k++)
                {
                    arr[k] += mat[j][k];
                }
            }
        }
        return max;
    }

    // 求子数组的最大累加和
    public static int MaxSumSubarray(int[] arr, int m)
    {
        int max = int.MaxValue;
        int cur = 0;
        for (int i = 0; i < m; i++)
        {
            cur += arr[i];
            max = Math.Max(max, cur);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }
}
